#include <iostream>
using namespace std;

int a[] = {3, 2, 1, 9, 5, 4, 6, 8, 7, 101, 95, 47, 65534, 1 << 30};
const int LEN = sizeof(a) / sizeof(int);
const int MAXN = 256;
int C[MAXN] = {0, };

void count_sort(int* A, int* B, int shift) {
    for (int i = 0; i < MAXN; i++) {
        C[i] = 0;
    }

    for (int i = 0; i < LEN; i++) {
        int v = (A[i] >> (shift * 8)) & 0xff;
        C[v] += 1;
    }

    for (int i = 1; i < MAXN; i++) {
        C[i] += C[i-1];
    }

    for (int i = LEN - 1; i >= 0; i--) {
        int v = (A[i] >> (shift * 8)) & 0xff;
        B[C[v] - 1] = A[i];
        C[v] -= 1;
    }
}

void randix_sort(int* A) {
    int* b = new int[LEN];

    for (int i = 0; i < 4; i++) {
        count_sort(A, b, i);

        for (int j = 0; j < LEN; j++) {
            A[j] = b[j];
        }
    }
}

void print(int* A, int len) {
    for (int i = 0; i < len; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
}

int main() {
    randix_sort(a);
    print(a, LEN);
    return 0;
}
